package com.jiajia.study.mylist.doublelist;

import com.jiajia.study.mylist.MyAbstractList;

/**
 * 双向链表
 * @author : zjj
 * @date : 2021/1/14 16:27
 */
public class MyLinkedList<E> extends MyAbstractList<E> {
    /**
     * 头节点
     */
    Node<E> first ;
    /**
     * 尾结点
     */
    Node<E> last;
    /**
     * 大小
     */
    int size;

    /**
     * 链表节点
     * @param <E>
     */
    private class Node<E>{
        Node<E> prev;
        Node<E> next;
        E element;

        public Node(Node<E> prev ,E element ,Node<E> next ){
            this.prev = prev;
            this.element = element;
            this.next = next;
        }
    }


    /**
     * 清空链表
     */
    @Override
    public void clear() {
        first = null;
        last = null;
        size = 0;

    }

    /**
     * 获取索引出的元素
     * @param index 元素的索引
     * @return      元素
     */
    @Override
    public E get(int index) {
        return node(index).element;
    }

    /**
     * 设置索引出元素的值
     * @param index     元素的索引
     * @param element   元素的值
     * @return          原来的值
     */
    @Override
    public E set(int index, E element) {
        Node<E> node = node(index);
        E oldElement = node.element;
        node.element = element;


        return oldElement;
    }

    /**
     * 往索引位置添加元素
     * @param index     元素的索引
     * @param element   元素的值
     */
    @Override
    public void add(int index, E element) {
        rangeCheckForAdd(index);

        // 插入尾部特殊处理
        if(index == size){
            Node<E> oldLast =last;
            Node<E> newNode = new Node<E>(oldLast,element,null);
            oldLast.next = newNode;
            if(oldLast == null){
                 first = last;
            }else {
                 oldLast.next = last;
            }
        }else {
            Node<E> node = node(index);
            Node<E> prev = node.prev;
            Node<E> newNode = new Node<E>(prev,element,node);

            // 插入头部特殊处理
            if(index == 0){
                first = newNode;
            }else {
                prev.next = newNode;
            }
        }
    }

    /**
     * 删除索引位置的节点
     * @param index 元素的索引
     * @return      删除的元素
     */
    @Override
    public E remove(int index) {

        Node<E> delNode = node(index);
        Node<E> prev = delNode.prev;
        Node<E> next = delNode.next;
        // 删除头节点
        if(index == 0){
            first = next;
        }else {
            prev.next = next;
        }
        // 删除尾结点
        if(index == size - 1){
            last = prev;
        }else {
            next.prev = prev;
        }


        return delNode.element;
    }

    /**
     * 找到元素的索引
     * @param element   元素
     * @return          索引
     */
    @Override
    public int indexOf(E element) {
        if (element == null) {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (node.element == null) {
                    return i;
                }

                node = node.next;
            }
        } else {
            Node<E> node = first;
            for (int i = 0; i < size; i++) {
                if (element.equals(node.element)) {
                    return i;
                }

                node = node.next;
            }
        }
        return ELEMENT_NOT_FOUND;
    }

    /**
     * 找到索引位置元素的节点
     * @param index 索引
     * @return      节点
     */
    private Node<E> node(int index){
        rangeCheck(index);
        if(index < (size >> 1)){
            Node<E> node = first;
            for (int i = 0; i < index; i++) {

                node = node.next;
            }
            return node;

        }else {
            Node<E> node = last;
            for (int i = size - 1; i > index ; i--) {
                node  = node.prev;
            }
            return node;
        }

    }
}
